package com.guaoran.algorithm.binary.search;

/**
 * @Auth gucheng
 * @Desc 切木头 ：有一些木头，把这些木头切割成一些长度相同的小段木头，需要得到小段的数目至少为K。希望得到的小段越长越好，你需要计算能够得到的小段木头的最大长度
 * @Date 2021/1/8 上午10:51
 */
public class WoodCut {

    public static void main(String[] args) {
        int[] nums = {232,124,456};
        int K = 7;
        System.out.println(woodCut(nums,K));
    }

    private static int woodCut(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return 0;
        }

        int start = 1;
        int end = getMax(nums);
        int mid;

        while(start + 1 < end){
            mid = start + (end - start)/2;
            int p = getPieces(nums,mid);
            if(p>=k){
                start = mid;
            }else {
                end = mid;
            }
        }
        if(getPieces(nums,end) >=k){
            return end;
        }
        if(getPieces(nums,start) >=k){
            return start;
        }
        return 0;
    }

    private static int getMax(int[] nums) {
        int max = nums[0];
        for (int num : nums) {
            if(max < num){
                max = num;
            }
        }
        return max;
    }

    /**
     * 获取木头切割的总小段数
     * @param nums 待切割的木头
     * @param woodLength 要切割的长度
     * @return
     */
    private static int getPieces(int[] nums, int woodLength) {
        int pieces = 0;
        for (int wood : nums) {
            pieces += wood/woodLength;
        }
        return pieces;
    }
}
